package dp;

//0-1背包问题
public class PackageProblem {

	// 每个物品的重量的数组
	public static final int[] w = { 2, 1, 3, 2, 1 };
	//与之对应的价值
	public static final int[] v = { 12, 10, 20, 15, 8 };

	public static void main(String[] args) {
		findMaxValue0_1(5, w, v);

	}

	/**
	 * //找到在固定容积内的价值最大值
	 * //values[i] = max{values[i - w[m]] + v[m]}, 其中i - w[m] >= 0
	 * //如果这样写，就不是0-1问题，而是所有的物品数量都是无穷的
	 */
	public static void findMaxValue(int packageWeight, int[] weights, int[] vals) {
		int[] values = new int[weights.length + 1];
		for (int i = 1; i <= weights.length; i++) {
			int temp = 0;
			int maxValue = 0;
			for (int j = 0; j < packageWeight; j++) {
				if (i - weights[j] >= 0) {
					temp = values[i - weights[j]] + vals[j];
					if (temp > maxValue) {
						maxValue = temp;
						values[i] = maxValue;
						System.out.println(i + "=i,values[" + i + "]="
								+ values[i]);
					}
				}
			}
		}
	}

	/*
	 * @param weight
	 */
	// values[i][j]表示取1,2，...i件物品容积为j的最大价值
	// values[i][j]=max{values[i][j-w[m]]+v[m],values[i-1][j]},其中i-w[m]>=0
	public static void findMaxValue0_1(int packageWeight, int[] weights, int[] vals) {
		// 此数组values[i]表示使用容量j装载前i件物品时的总价值
		int[][] values = new int[weights.length + 1][packageWeight + 1]; 
		// 依次从物品中取，这样就保证了只取一次
		values[0][0] = 0;
		for (int i = 1; i <= weights.length; i++) {
			// 初始化价值
			values[i][0] = 0;
			int temp = 0;
			for (int j = 1; j <= packageWeight; j++) {
				// 如果j大于w[i-1],还可以继续放物品
				if (j - weights[i - 1] >= 0) {
					temp = values[i - 1][j - weights[i - 1]] + vals[i - 1];
					if (values[i - 1][j] > temp) {
						values[i][j] = values[i - 1][j];
						// System.out.println(i + "=i,values[" + i + "][" + j
						// + "]=" + values[i][j]);
					} else {
						values[i][j] = temp;
					}
				} else {
					// 不然的话，就等于values[i-1][j];
					values[i][j] = values[i - 1][j];
				}
			}
		}
		for (int i = 0; i < values.length; i++) {
			for (int j = 0; j < values[i].length; j++) {
				System.out.print(values[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	//对控件进行压缩
	public void findMaxValue0_1Zip(int packageWeight, int[] weights, int[] vals) {
		// 此数组values[i][j]表示使用容量j装载前i件物品时的总价值
		int[] values = new int[packageWeight + 1];
		// 依次从物品中取，这样就保证了只取一次
		values[0] = 0;
		for (int i = 1; i <= weights.length; i++) {
			// 初始化价值
			values[0] = 0;
			int temp = 0;
			for (int j = packageWeight; j >= weights[i - 1]; j--) {
				// 如果j大于w[i-1],还可以继续放物品
				
					temp = values[j - weights[i - 1]] + vals[i - 1];
					if (values[j] < temp) {
						values[j] = temp;
					}
			}
		}
		int max = 0;

		for (int j = 0; j < values.length; j++) {
			max = Math.max(max, values[j]);
		}
		System.out.println(max);
	}
}
/**
 * 
 //for(int k=0;k<w.length;k++){ //if (j - w[k] >= 0) { // temp = values[i -
 * 1][j - w[k]] + v[k]; // if (temp > maxValue) { // maxValue = temp; //
 * values[i][j] = maxValue; // System.out.println(i + "=i,values[" + i + "]["+
 * j+"]=" // + values[i][j]); // } //} else { // values[i][j] = values[i -
 * 1][j]; //} //}
 */
